Technical Field
This disclosure relates to designing embedded control software, including identifying at least one contraction metric that satisfies contraction conditions for a design of a dynamical system.
Description of Related Art
Embedded control software may be developed using a model-based development (MBD) paradigm. MBD may provide a framework under which system design specifications and performance models may be created.
One model in the MBD paradigm is the closed-loop model. This model may represent the composition of a plant model and a model of control software.
The plant model may be an encapsulation of dynamical aspects of the physical system for which the control software is being designed. In an automotive context, for example, a plant model may describe the dynamical behavior of an automotive engine, intake and exhaust manifolds, sensors, actuators, and/or other physical components. A plant model may be described as a dynamical system, which may be a mathematical model of a system described by a fixed number of states, and with ordinary differential equations (ODEs) describing the evolution of these states over time. In an automotive context, the states may represent physical quantities, such as pressures, masses of air, amount of fuel, and temperature.
The model of the control software or the controller model may be a logical abstraction of real-time software controlling the plant. The description of the controller model may be similar to that of a computer program, and may thus be associated with inputs, outputs, memory, and arithmetic and logical computations. The controller model may be described in a visual, block-diagram based, model-based design language.
A closed-loop model can be used to study and analyze properties of a control system. One problem for MBD may be to determine whether certain quantities of interest always remain within a desired operating regime. In the computer science literature, such a regime is sometimes called the safe region, and its set-complement the unsafe region. The problem of checking if any time-varying behavior of a given closed-loop model ever reaches an unsafe region is called the reachability problem. The reachability problem may be intractable, meaning that no computer algorithm may be able to solve it.
Another problem may be that of checking asymptotic behavior of a control system. This may mean analyzing the limiting behavior of system over arbitrarily long (infinite) time durations. All behaviors of the control system may need to converge to a desired reference behavior for the system to have desirable asymptotic behavior.
The two problems described above—the reachability problem and the problem of analyzing asymptotic behavior—may both be addressed by contraction analysis. This technique relies on showing the existence of a contraction metric for the closed-loop model.
Contraction analysis may be a relatively new development for control systems See W. Lohmiller and J. J. E. Slotine, “On contraction analysis for non-linear systems,” Automatica, 34(6):683-696, 1998; F. Forni and R. Sepulchre, “A differential lyapunov framework for contraction Analysis,” CoRR, abs/1208.2943, 2012. Techniques to obtain contraction metrics may exist only for specific classes of dynamical systems.
Mathematical definitions for contraction metrics were presented in W. Lohmiller and J. J. E. Slotine, “On contraction analysis for non-linear systems,” Automatica, 34(6):683-696, 1998 and extended in F. Forni and R. Sepulchre, “A differential lyapunov framework for contraction Analysis,” CoRR, abs/1208.2943, 2012. In E. M. Aylward, P. A. Parrilo, and J.-J. E. Slotine, “Stability and robustness analysis of nonlinear systems via contraction metrics and sos programming,” Automatica, 44(8):2163{2170, August 2008, SoS tools were used for systems with polynomial dynamics, i.e., polynomial expressions on the right-hand-sides of the system ODEs. They may require full knowledge of the system dynamics, and may reduce the analytic problem to finding the feasible solution of a semi-definite program. This technique may not work for systems with non-polynomial dynamics. The contraction metrics found by this technique may also be unsound and non-robust.
Contraction analysis is closely related to the notion of incremental stability. See D. Angeli, “A Lyapunov approach to incremental stability properties,” IEEE Trans. on Automatic Control, 47(3):410-421. Work in control systems technology may build on the notion of incremental stability for safety verification of nonlinear switched systems. See P. S. Duggirala, S. Mitra, and M. Viswanathan, “Verification of annotated models from executions,” In Proc. of the Conference on Embedded Software, pages 26:1-26:10, 2013; Z. Huang and S. Mitra, “Proofs from simulations and modular annotations,” In Proc. of Hybrid Systems: Computation and Control, 2014. A key idea in this work may be that different kinds of annotations (including contraction metrics) can be used to aid safety verification. An assumption may be that these annotations are provided by the designer. Hence, this work may not provide any systematic approach to generating such annotations.
Semi-definite programming is an optimization technique to address several problems in control design. See S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan, “Linear Matrix Inequalities in System and Control Theory,” volume 15, SIAM, 1994; L. Vandenberghe and S. Boyd. Semidefinite Programming. SIAM Review, 38(1):49{95, 1996. Open-source software tools exist for solving these problems. See J. Löfberg. “YALMIP: A toolbox for modeling and optimization in MATLAB,” In Proc. of the CACSD Conference, 2004; J. F. Sturm, Using SeDuMi 1.02, “A MATLAB Toolbox for Optimization over Symmetric Cones,” Optimization Methods and Software, 11/12(1-4):625-653, 1999. The techniques may be computationally efficient, even for large industrial problems.
Decision procedures for nonlinear arithmetic queries are an area of research in the computer science literature. Open-source software tools based on interval constraint propagation techniques may exist for solving such queries. See S. Gao, J. Avigad, and E. M. Clarke, “δ-complete decision procedures for satisfiability over the reals,” In J. Automated Reasoning, pages 286-300, 2012. The tools may be computationally efficient for problems of a reasonable size.
In previous work, a technique was described to use simulations to compute Lyapunov functions for nonlinear dynamical systems. See J. Kapinski, J. V. Deshmukh, S. Sankaranarayanan, and N. Arechiga, “Simulation-guided lyapunov analysis for hybrid dynamical systems,” In Proc. of Hybrid Systems: Computation and Control, pages 133-142, 2014 Lyapunov functions may also be used to address the reachability problem; however, the set of reachable states as estimated by using Lyapunov analysis can be significantly conservative and thusly an imprecise over-estimation. Lyapunov analysis may also be imprecise when analyzing asymptotic behavior of system trajectories with respect to each other.
Contraction analysis allows greater precision in analyzing asymptotic behavior, as well as for reachability analysis as compared to extant techniques. Existing methods for obtaining contraction metrics for nonlinear dynamical systems may be restricted to the class of polynomial dynamical systems. Current methods may not provide any mathematical soundness guarantees for the contraction metrics obtained, and may also suffer from numerical robustness in the solutions.